<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Winnow (algorithm)</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Winnow_(algorithm)"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Winnow_algorithm rootpage-Winnow_algorithm skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Winnow (algorithm)</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>The <b>winnow algorithm</b><sup id="cite_ref-littlestone88_1-0" class="reference"><a href="#cite_note-littlestone88-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> is a technique from <a href="Machine_learning" title="Machine learning">machine learning</a> for learning a <a href="Linear_classifier" title="Linear classifier">linear classifier</a> from labeled examples. It is very similar to the <a href="Perceptron" title="Perceptron">perceptron algorithm</a>. However, the perceptron algorithm uses an additive weight-update scheme, while Winnow uses a <a href="Multiplicative_Weight_Update_Method" class="mw-redirect" title="Multiplicative Weight Update Method">multiplicative scheme</a> that allows it to perform much better when many dimensions are irrelevant (hence its name <a href="Winnowing" title="Winnowing">winnow</a>). It is a simple algorithm that scales well to high-dimensional data. During training, Winnow is shown a sequence of positive and negative examples. From these it learns a decision <a href="Hyperplane" title="Hyperplane">hyperplane</a> that can then be used to label novel examples as positive or negative. The algorithm can also be used in the <a href="Online_machine_learning" title="Online machine learning">online learning</a> setting, where the learning and the classification phase are not clearly separated.
</p>
<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>
<p>The basic algorithm, Winnow1, is as follows. The instance space is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=\{0,1\}^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<msup>
<mo fence="false" stretchy="false">}</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X=\{0,1\}^{n}}</annotation>
</semantics>
</math></span><img src="./9027ead426bee016c64e4e95846fc9bcb2ca9385.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.981ex; height:2.843ex;" alt="{\displaystyle X=\{0,1\}^{n}}" loading="lazy"></span>, that is, each instance is described as a set of <a href="Boolean-valued" title="Boolean-valued">Boolean-valued</a> <a href="Features_(pattern_recognition)" class="mw-redirect" title="Features (pattern recognition)">features</a>. The algorithm maintains non-negative weights <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>
</semantics>
</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span> for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in \{1,\ldots ,n\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
<mo>∈<!-- ∈ --></mo>
<mo fence="false" stretchy="false">{</mo>
<mn>1</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mi>n</mi>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i\in \{1,\ldots ,n\}}</annotation>
</semantics>
</math></span><img src="./7898b0be3a01bf31af25ec96239b2a7b96b77055.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.703ex; height:2.843ex;" alt="{\displaystyle i\in \{1,\ldots ,n\}}" loading="lazy"></span>, which are initially set to 1, one weight for each feature. When the learner is given an example <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},\ldots ,x_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (x_{1},\ldots ,x_{n})}</annotation>
</semantics>
</math></span><img src="./7935f7983d8a5ae59fea84efe65415235fa7c47b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.92ex; height:2.843ex;" alt="{\displaystyle (x_{1},\ldots ,x_{n})}" loading="lazy"></span>, it applies the typical prediction rule for linear classifiers:
</p>
<ul><li><b>If</b> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</munderover>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>></mo>
<mi mathvariant="normal">Θ<!-- Θ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }</annotation>
</semantics>
</math></span><img src="./889e7a1b139588d35de32b6c0923f290ecf95de7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.242ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>\Theta }" loading="lazy"></span>, <b>then</b> predict 1</li>
<li><b>Otherwise</b> predict 0</li></ul>
<p>Here <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>
</semantics>
</math></span><img src="./bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span> is a real number that is called the <i>threshold</i>. Together with the weights, the threshold defines a dividing hyperplane in the instance space. Good bounds are obtained if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta =n/2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo>=</mo>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta =n/2}</annotation>
</semantics>
</math></span><img src="./9d78bd618c137386c212e353aae2cc6a82b61d4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.626ex; height:2.843ex;" alt="{\displaystyle \Theta =n/2}" loading="lazy"></span> (see below).
</p><p>For each example with which it is presented, the learner applies the following update rule:
</p>
<ul><li>If an example is correctly classified, do nothing.</li>
<li>If an example is predicted incorrectly and the correct result was 0, for each feature <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}=1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x_{i}=1}</annotation>
</semantics>
</math></span><img src="./a230692f2eb10d5fc1ead43dd83d75f3b592a09b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}=1}" loading="lazy"></span>, the corresponding weight <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>
</semantics>
</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span> is set to 0 (demotion step).
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall x_{i}=1,w_{i}=0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">∀<!-- ∀ --></mi>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \forall x_{i}=1,w_{i}=0}</annotation>
</semantics>
</math></span><img src="./3de5a200d9e1ea9c0972e97a90f436be5cfc984c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.441ex; height:2.509ex;" alt="{\displaystyle \forall x_{i}=1,w_{i}=0}" loading="lazy"></span></dd></dl></li>
<li>If an example is predicted incorrectly and the correct result was 1, for each feature <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}=1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x_{i}=1}</annotation>
</semantics>
</math></span><img src="./a230692f2eb10d5fc1ead43dd83d75f3b592a09b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}=1}" loading="lazy"></span>, the corresponding weight <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>
</semantics>
</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span> multiplied by <span class="texhtml mvar" style="font-style:italic;">α</span>(promotion step).
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall x_{i}=1,w_{i}=\alpha w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">∀<!-- ∀ --></mi>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mi>α<!-- α --></mi>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \forall x_{i}=1,w_{i}=\alpha w_{i}}</annotation>
</semantics>
</math></span><img src="./c0155ee35dc2f3e8a7418776b5f96d91ae24a91c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.23ex; height:2.509ex;" alt="{\displaystyle \forall x_{i}=1,w_{i}=\alpha w_{i}}" loading="lazy"></span></dd></dl></li></ul>
<p>A typical value for <span class="texhtml mvar" style="font-style:italic;">α</span> is 2.
</p><p>There are many variations to this basic approach. <i>Winnow2</i><sup id="cite_ref-littlestone88_1-1" class="reference"><a href="#cite_note-littlestone88-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> is similar except that in the demotion step the weights are divided by <span class="texhtml mvar" style="font-style:italic;">α</span> instead of being set to 0. <i>Balanced Winnow</i> maintains two sets of weights, and thus two hyperplanes. This can then be generalized for <a href="Multi-label_classification" title="Multi-label classification">multi-label classification</a>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Mistake_bounds">Mistake bounds</h2></div>
<p>In certain circumstances, it can be shown that the number of mistakes Winnow makes as it learns has an <a href="Upper_and_lower_bounds" title="Upper and lower bounds">upper bound</a> that is independent of the number of instances with which it is presented. If the Winnow1 algorithm uses <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha >1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>α<!-- α --></mi>
<mo>></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \alpha >1}</annotation>
</semantics>
</math></span><img src="./17d81dbbc4786493c7b8548cc324a978d7cf5dbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;" alt="{\displaystyle \alpha >1}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \geq 1/\alpha }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo>≥<!-- ≥ --></mo>
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mi>α<!-- α --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta \geq 1/\alpha }</annotation>
</semantics>
</math></span><img src="./dfd6b744a3a878e94d987e9800917b928ac6a429.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.719ex; height:2.843ex;" alt="{\displaystyle \Theta \geq 1/\alpha }" loading="lazy"></span> on a target function that is a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-literal monotone disjunction given by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\cup \cdots \cup x_{i_{k}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>i</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msub>
<mo>∪<!-- ∪ --></mo>
<mo>⋯<!-- ⋯ --></mo>
<mo>∪<!-- ∪ --></mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>i</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\cup \cdots \cup x_{i_{k}}}</annotation>
</semantics>
</math></span><img src="./76070d92c3cd6dc17f68f8091a4c335c65840d02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:30.135ex; height:3.009ex;" alt="{\displaystyle f(x_{1},\ldots ,x_{n})=x_{i_{1}}\cup \cdots \cup x_{i_{k}}}" loading="lazy"></span>, then for any sequence of instances the total number of mistakes is bounded by:
<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>α<!-- α --></mi>
<mi>k</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>α<!-- α --></mi>
</mrow>
</msub>
<mo><!-- --></mo>
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo>+</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>n</mi>
<mi mathvariant="normal">Θ<!-- Θ --></mi>
</mfrac>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}</annotation>
</semantics>
</math></span><img src="./258bbed5460bfaa492e2f2351545f5c643ce38c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:20.447ex; height:4.843ex;" alt="{\displaystyle \alpha k(\log _{\alpha }\Theta +1)+{\frac {n}{\Theta }}}" loading="lazy"></span>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-littlestone88-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-littlestone88_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-littlestone88_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"> Nick Littlestone (1988). "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm", <a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1022869011914"><i>Machine Learning</i> 285–318(2)</a>.</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">
Nick Littlestone (1989). "Mistake bounds and logarithmic linear-threshold learning algorithms".
Technical report UCSC-CRL-89-11, University of California, Santa Cruz.</span>
</li>
</ol></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2020-02-13" href="https://en.wikipedia.org/wiki/?title=Winnow_(algorithm)&oldid=940538455">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>